class Solution {
    public boolean exist(char[][] board, String word) {
        int[][] nextPos = {{0,1}, {1,0}, {0,-1}, {-1, 0}};
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                boolean flag = dfs(board, visited, word, i, j, 0, nextPos);
                if(flag)    return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, boolean[][] visited, String word, int x, int y, int index, int[][] nextPos){
        char c = word.charAt(index);
        if(c != board[x][y]){
            return false;
        }else if(index == word.length() - 1){
            return true;
        }
        visited[x][y] = true;
        boolean res = false;
        for(int i = 0; i < 4; i++){
            int newX = x + nextPos[i][0];
            int newY = y + nextPos[i][1];
            if(newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length){
                continue;
            }
            if(!visited[newX][newY]){
                boolean flag = dfs(board, visited,word, newX, newY, index + 1, nextPos);
                if(flag){
                    res = true;
                    break;
                }
            }
        }
        visited[x][y] = false;
        return res;
    }
}